// 返回两个无环链表相交的第一个节点
// 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/
public class Code01_IntersectionOfTwoLinkedLists {
    // 提交时不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    // 提交如下的方法
    public static ListNode getIntersectionNode(ListNode h1, ListNode h2) {
        // 如果其中一个链表为空，直接返回null，因为不存在相交节点
        if (h1 == null || h2 == null) {
            return null;
        }
        ListNode a = h1;
        ListNode b = h2;
        int diff = 0;
        // 计算链表h1的长度（不包含头节点），同时记录长度差值
        while (a.next!= null) {
            a = a.next;
            diff++;
        }
        // 计算链表h2的长度（不包含头节点），并更新长度差值
        while (b.next!= null) {
            b = b.next;
            diff--;
        }
        // 如果两个链表的尾节点不相同，说明两个链表不相交，直接返回null
        if (a!= b) {
            return null;
        }
        // 根据长度差值调整指针的起始位置
        // 如果diff >= 0，将a指向h1的头节点，b指向h2的头节点
        // 否则将a指向h2的头节点，b指向h1的头节点
        if (diff >= 0) {
            a = h1;
            b = h2;
        } else {
            a = h2;
            b = h1;
        }
        diff = Math.abs(diff);
        // 将较长链表的指针向前移动diff步，使得两个指针到相交节点的距离相同
        while (diff--!= 0) {
            a = a.next;
        }
        // 同时移动a和b指针，直到找到相交节点
        while (a!= b) {
            a = a.next;
            b = b.next;
        }
        // 返回相交节点，如果没有相交则返回null
        return a;
    }
}